/*
一个30 * 35 的表格，
左上角为起点，
右下角为终点，

问： 
从起点出发，
只能向右或向下移动，
到终点有几种可能。
*/
#include "junix.h"

int f(int n,int m) {
	assert(n>0 && m>0);
	if (n==1 || m==1) return 1;
	return f(n-1,m)+f(n,m-1);
}

int f2(int n,int m) {
	assert(n>0 && m>0);
	if (n==1 || m==1) return 1;
	typedef std::vector<std::vector<int> > MATRIX;
	MATRIX matrix(n+1,std::vector<int>(m+1));

	for (int i=1;i<=n;i++) 
		matrix[i][1]=1;

	for (int i=1;i<=m;i++) 
		matrix[1][i]=1;

	for (int i=2;i<=n;i++) 
		for (int j=2;j<=m;j++) 
			matrix[i][j] = matrix[i-1][j]+matrix[i][j-1];
		
	return matrix[n][m];
}

int main(){
	int sz = 15;
	std::cout<<f2(sz,sz)<<std::endl;
	std::cout<<f(sz,sz)<<std::endl;
}
